package com.syxbyi.yudong.class01;

public class MergeTwoSortedLists {

    static class ListNode {
        int val;
        ListNode next;
    }

    public static ListNode mergeTwoSortedLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode head;
        ListNode p = l1;                // 直接用 l1 也可以，但是 p 比较直观
        ListNode q = l2;
        if (l1.val <= l2.val) {
            head = l1;
            p = p.next;
        } else {
            head = l2;
            q = q.next;
        }
        ListNode tail = head;           // tail != null
        while (p != null) {
            if (q == null) {
                tail.next = p;
                return head;
            }
            if (p.val <= q.val) {       // add ListNode p to tail
                tail.next = p;
                tail = p;
                p = p.next;
            } else {
                tail.next = q;
                tail = q;
                q = q.next;
            }
        }
        // p == null && q != null
        tail.next = q;
        return head;
    }

}
